package com.zlk.algorithm.algorithm.dynamicPlan.arraySum;

// 打家劫舍 IV
// 沿街有一排连续的房屋。每间房屋内都藏有一定的现金
// 现在有一位小偷计划从这些房屋中窃取现金
// 由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
// 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
// 给你一个整数数组 nums 表示每间房屋存放的现金金额
// 第i间房屋中放有nums[i]的钱数
// 另给你一个整数k，表示小偷需要窃取至少 k 间房屋
// 返回小偷需要的最小窃取能力值
// 测试链接 : https://leetcode.cn/problems/house-robber-iv/
public class Code05_HouseRobberIV {

    public static void main(String[] args) {
        System.out.println(minCapability(new int[]{2, 3, 5, 9}, 2));
    }

    public static int minCapability(int[] nums, int k) {
        return f(nums,k);
    }

    private static int f(int[] nums, int k) {
        if(nums.length<k){
            return -1;
        }
        if(nums.length==k&&k==1){
            return nums[0];
        }
        int r = 0;
        for (int i = 0; i < nums.length; i++) {
            r = Math.max(r,nums[i]);
        }
        int l = 0;
        int ans = 0;
        while (l<=r){
            int mid = l+((r-l)>>1);
            if(f(mid,nums,k)){
                r = mid-1;
                ans = mid;
            }else{
                l  = mid+1;
            }
        }
        return ans;
    }

    /**
     * dp含义以i位置结尾 的最大房间数
     * 由于不相邻所以dp[i]依赖dp[i-2] 与dp[i-3]
     * 为啥不依赖dp[i-4]应为依赖dp[i-4]肯定依赖dp[i-2] 已经包含
     * @param mid
     * @param nums
     * @param k
     * @return
     */
    private static boolean f(int mid, int[] nums, int k) {
        //dp含义  i 位置结尾 符合条件的房间数
        int[] dp = new int[nums.length];
        dp[0] = mid>=nums[0]?1:0;
        for (int i = 1; i < nums.length; i++) {
            int cur = nums[i];
            int p1=0;
            int p2=0;
            if(i-2>=0){
                p1=dp[i-2];
            }
            if(i-3>=0){
                p2=dp[i-3];
            }
            //dp[i]=cur+Math.max(p1,p2);
            dp[i]=mid>=cur?1+Math.max(p1,p2):Math.max(p1,p2);
        }
        return Math.max(dp[nums.length-1],dp[nums.length-2])>=k;
    }

    /**
     * dp【i】0到i的的最大房间数
     *  要i  Math.max(nums[i]+dp[i-2],nums[i])    (考虑dp[i-2]可能负数)
     *  不要i dp[i-1]
     * @param nums
     * @return
     */
    private static boolean f2(int ability, int[] nums, int k) {
        //dp含义  i 位置结尾 符合条件的房间数
        int[] dp = new int[nums.length];
        dp[0] = ability>=nums[0]?1:0;
        dp[1] = Math.max(ability>=nums[1]?1:0,dp[0]);
        for (int i = 2; i < nums.length; i++) {
            int p1 = dp[i-1];
            int p2 = ability>=nums[i]?1+dp[i-2]:dp[i-2];
            dp[i] = Math.max(p1,p2);
        }
        return dp[nums.length-1]>=k;
    }
}
